1. Field of the Invention
The present invention relates to a process for manipulating images using compressed run length data of the image.
2. Description of the Related Art
An image skeleton represents the basic structure of an image and is created by decomposing the widths of raster objects in the image to uniform single pixel widths. This simplifies the task of certain recognition systems from character recognition to geometrical recognition.
The current state of the art provides a process for skeletonization of an image by stripping one layer of pixels after another. The process continues until the set of pixels left form a one pixel wide line and is defined as separating two "off" areas. This process is known as raster "thinning" or "erosion."
The problems associated with the current skeletonization processes include their relatively slow speed and extensive memory utilization requirements. In order to skeletonize the image using the current techniques, two copies of the image must be maintained in memory. For large images, this could mean storing an extraordinary, amount of data. The larger the data file, the greater the access time. Therefore, the process of data retrieval and storage increases in time with the increased amount of data stored.
Also, every pixel in the image is evaluated regardless of whether the pixel will be removed or ignored. This requires a substantial increase in the number of points to be evaluated and increases the amount of time required to complete the process.
The prior art discloses a number of devices utilizing appropriated methods and apparatus for skeletonization of images used in pattern recognition. For example, U.S. Pat. No. 3,975,709 to Beun et al. and U.S. Pat. No. 5,224,179 to Denker et al. disclose methods of image thinning or skeletonization utilizing at least 3.times.3 grid pixel by pixel analysis to thin a character of interest.
Another reference, U.S. Pat. No. 5,335,290 to Cullen et al., teaches a character recognition system by extracting run lengths for each scanline from the bit mapped representation of the document image and classifying the data as image, text or as a horizontal or vertical line. However, there is no teaching of the process of skeletonization by run length comparison which is needed to increase speed of the pattern recognition.
Still another reference, U.S. Pat. No. 4,491,960 to Brown, describes a pattern comparison system wherein a raster scan of a hand print produces a topography to be compared to a given parameters for identification.
Yet another reference, Zhang et al., "A Fast Parallel Algorithm for Thinning Digital Patterns", discloses skeletonization via pixel by pixel comparison and removal of subsequent outer pixels for character thinning.
However, the prior art fails to address the problem of size of data files and speed of skeletonization and does not disclose, teach or even suggest the embodiments of the claimed invention.